#include "BTreeNode.h"

BTLeafNode::BTLeafNode()
{
	int* num_entries = (int*)buffer;
	*num_entries = 1;

	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];

	entries[0].rid.pid = -1;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int* num_entries = (int*)buffer;

	//number of entries includes the final entry containing just the 
	//pid of the next leaf node, so number of keys = #entries - 1
	return *num_entries - 1;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int* num_entries = (int*)buffer;
	if(*num_entries == MAX_ENTRIES)
		return RC_NODE_FULL;

	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];
	int insertion_index = 0;
	for(; insertion_index < *num_entries - 1; insertion_index++)
		if(entries[insertion_index].key > key)
			break;

	for(int j = *num_entries - 1; j >= insertion_index; j--)
		entries[j + 1] = entries[j];

	entries[insertion_index].key = key;
	entries[insertion_index].rid = rid;

	*num_entries = *num_entries + 1;
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * This does not fix the next node pointers of the current node and sibling!
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int ret;

	int* num_entries = (int*)buffer;
	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];

	int insertion_index = 0;
	for(; insertion_index < *num_entries - 1; insertion_index++)
		if(entries[insertion_index].key > key)
			break;
	
	//find the middle entry, the very last entry is always a pointer to
	//the next leaf so exclude it, but also include the one being added
	int split_point = (*num_entries) / 2;
	
	//if the new entry stays in this node (the "left" node)
	if(insertion_index < split_point)
	{
		//transfer over all the nodes past the midpoint
		for(int i = split_point - 1; i < *num_entries - 1; i++)
		{
			ret = sibling.insert(entries[i].key, entries[i].rid);
			if(ret != 0)
				return ret;	
		}

		//before inserting the new node, fix the node so that it only
		//contains the remaining nodes (and fix the next node ptr)
		entries[split_point - 1] = entries[*num_entries - 1];
		*num_entries = split_point;

		//insert the new node
		ret = insert(key, rid);
		if(ret != 0)
			return ret;
	} else {
		//transfer over all the nodes past the midpoint
		for(int i = split_point; i < *num_entries - 1; i++)
		{
			ret = sibling.insert(entries[i].key, entries[i].rid);
			if(ret != 0)
				return ret;	
		}

		//fix the current node so that it only contains remaining nodes
		//(also fix the next node ptr)
		entries[split_point] = entries[*num_entries - 1];
		*num_entries = split_point + 1;

		//insert the new node into the sibling
		ret = sibling.insert(key, rid);
		if(ret != 0)
			return ret;
	}

	//store the first key in the sibling into siblingKey
	RecordId first_rid;
	ret = sibling.readEntry(0, siblingKey, first_rid);
	if(ret != 0)
		return ret;

	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int num_keys = getKeyCount();
	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];
	
	for(int i = 0; i < num_keys; i++)
	{
		if(entries[i].key >= searchKey)
		{
			eid = i;
			return 0;
		}
	}
	return RC_END_OF_TREE;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	if(eid >= getKeyCount())
		return -1;

	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];
	key = entries[eid].key;
	rid = entries[eid].rid;

	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	int* num_entries = (int*)buffer;
	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];

	return entries[*num_entries - 1].rid.pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	int* num_entries = (int*)buffer;
	LNEntry* entries = (LNEntry*)&buffer[START_ENTRIES];
	
	entries[*num_entries - 1].rid.pid = pid;
	return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	 pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int* num_entries = (int*)buffer;
	return *num_entries - 1;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
	int* num_entries = (int*)buffer;
	if(*num_entries == MAX_ENTRIES)
		return RC_NODE_FULL;

	NLNEntry* entries = (NLNEntry*)&buffer[START_ENTRIES];
	int insertion_index = 0;
	for(; insertion_index < *num_entries - 1; insertion_index++)
		if(entries[insertion_index].key > key)
			break;
	
	//if the new entry is being inserted anywhere but at the end of the node
	if(insertion_index != *num_entries - 1)
	{
		for(int j = *num_entries - 1; j >= insertion_index; j--)
			entries[j + 1] = entries[j];

		entries[insertion_index].key = key;
		entries[insertion_index].pid = pid;
	} else {
		//otherwise the pid is going to be inserted to the right
		//instead of to the left
		
		entries[insertion_index].key = key;
		entries[insertion_index + 1].pid = pid;
	}

	*num_entries = *num_entries + 1;
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int ret;

	int* num_entries = (int*)buffer;
	NLNEntry* entries = (NLNEntry*)&buffer[START_ENTRIES];

	int insertion_index = 0;
	for(; insertion_index < *num_entries - 1; insertion_index++)
		if(entries[insertion_index].key > key)
			break;

	//if the new entry is being inserted anywhere but at the end of the node
	if(insertion_index != *num_entries - 1)
	{
		for(int j = *num_entries - 1; j >= insertion_index; j--)
			entries[j + 1] = entries[j];

		entries[insertion_index].key = key;
		entries[insertion_index].pid = pid;
	} else {
		//otherwise the pid is going to be inserted to the right
		//instead of to the left
		
		entries[insertion_index].key = key;
		entries[insertion_index + 1].pid = pid;
	}

	*num_entries = *num_entries + 1;
	
	//find the middle entry, the very last entry is always just a pointer
	//so exclude it
	int split_point = (*num_entries - 1) / 2;

	//transfer over all nodes to the right of the middle to the sibling
	sibling.initializeRoot(entries[*num_entries - 2].pid, entries[*num_entries - 2].key, entries[*num_entries - 1].pid);
	for(int i = *num_entries - 3; i > split_point; i--)
	{
		ret = sibling.insert(entries[i].key, entries[i].pid);
		if(ret != 0)
			return ret;
	}
	
	//fix the current node so that it only contains the nodes on the
	//left of the middle
	*num_entries = split_point + 1;

	//pass back the middle key
	midKey = entries[split_point].key;

	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int* num_entries = (int*)buffer;
	NLNEntry* entries = (NLNEntry*)&buffer[START_ENTRIES];

	for(int i = 0; i < *num_entries - 1; i++)
	{
		if(entries[i].key > searchKey)
		{
			pid = entries[i].pid;
			return 0;
		}
	}

	pid = entries[*num_entries - 1].pid;
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	int* num_entries = (int*)buffer;
	NLNEntry* entries = (NLNEntry*)&buffer[START_ENTRIES];

	*num_entries = 2;
	entries[0].key = key;
	entries[0].pid = pid1;
	entries[1].pid = pid2;

	return 0;
}
